package zuochengyun;

//最长无重复子串
public class LongestUnrepeatSubString {

	public int maxUnique(String str){
		if(str == null || str.equals("")){
			return 0;
		}
		char[] chas = str.toCharArray();
		int[] map = new int[256];	//表示某个字符最近一次出现的位置
		for(int i = 0; i < 256; i++){
			map[i] = -1;	//初始全部为-1，表示都没有出现
		}
		int len = 0;
		//pre表示当前遍历到字符str[i],必须以str[i - 1]字符结尾的情况下，最长无重复子串的开始位置的前一个位置
		int pre = -1;
		int curLength = 0;
		for (int i = 0; i < chas.length; i++) {
			//判断pre和最近一次出现str[i]字符的位置(假设为a位置)谁离i位置近
			//如果pre位置在a位置的左边，由于肯定不能包括a位置(这个位置为str[i])
			//所以无重复子串为str[a + 1 ... i]
			//如果pre位置在a位置的右边，pre表示的以str[i - 1]字符结尾的情况下，最长无重复子串的开始位置的前一个位置
			//所以无重复子串肯定不能包括pre,为str[pre + 1 ... i]
			pre = Math.max(pre, map[chas[i]]);
			curLength = i - pre;
			len = Math.max(len, curLength);
			map[chas[i]] = i;
		}
		return len;
	}
}
